package offer

/*
时间复杂度：O(N*(sum-target))
空间复杂度：O(sum-target)

a b

sum=a+b => a=sum-b
target = a-b => sum-2b = target => b = (sum-target)/2

2*a=sum+target
a=(sum+target)/2
b=(sum-target)/2
*/
func findTargetSumWays(nums []int, target int) int {
	sum := 0
	for _, v := range nums {
		sum += v
	}
	diff := sum - target
	// nums[i]>=0 所以当diff==0时是可以取某个nums[i]的
	if diff < 0 || diff%2 != 0 {
		return 0
	}
	nei := diff / 2
	// 1.定义一个长度为目标值+1的dp
	// 2.遍历存储所有物品的nums数组
	// 3.内层循环遍历target -> nei
	//	for i := nei; i >= v; i--
	//  dp[i] += dp[i-v]  => dp[i] = dp[i] + dp[i-v]
	// 假设当前遍历到第k个物体，那么会出现两种状态
	// 1.不取: 取到和为nei的方法数就是dp[i] (这里的dp[i]是值在前k-1个物品中取到和为nei的方法数)
	// 2.取：dp[i-v] 表示的是在前k-1个物品中取到值为i-v的方法数
	dp := make([]int, nei+1)
	dp[0] = 1
	for _, v := range nums {
		for i := nei; i >= v; i-- {
			dp[i] += dp[i-v]
		}
	}
	return dp[nei]
}
